package com.example.demo.arithmetic.datastructure.tree;

import java.util.LinkedList;

// 二叉搜索树的范围和
// 给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
//      4
//     / \
//    2   6
//   / \
//  1   3
public class Leetcode938_2 {
    public int rangeSumBST(TreeNode root, int low, int high) {
        TreeNode p = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        int sum = 0;
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            if (p.val >= low && p.val <= high) {
                sum += p.val;
            }
            p = p.right;
        }
        return sum;
    }


}
